package com.zj.study.map;


/**
 * @author 赵赳
 * @since 2021/12/16 17:21
 */
public class MyHashMap<K, V> {


  /**
   * 节点类
   *
   * @param <K>
   * @param <V>
   */
  static class Node<K, V> {

    //键值对
    private final K key;
    private V value;

    //链表，后继
    private Node<K, V> next;

    public Node(K key, V value) {
      this.key = key;
      this.value = value;
    }

    public Node(K key, V value, Node<K, V> next) {
      this.key = key;
      this.value = value;
      this.next = next;
    }

    public final String toString() {
      return key + "=" + value;
    }
  }


  //默认容量
  final int DEFAULT_CAPACITY = 16;
  //负载因子
  final float LOAD_FACTOR = 0.75f;
  //HashMap的大小
  private int size;
  //桶数组
  Node<K, V>[] buckets;


  /**
   * 无参构造器，设置桶数组默认容量
   */
  @SuppressWarnings("unchecked")
  public MyHashMap() {
    buckets = new Node[DEFAULT_CAPACITY];
    size = 0;
  }

  /**
   * 有参构造器，指定桶数组容量
   *
   * @param capacity 初始化容量
   */
  @SuppressWarnings("unchecked")
  public MyHashMap(int capacity) {
    buckets = new Node[capacity];
    size = 0;
  }

  /**
   * 哈希函数，获取地址
   *
   * @param key key
   * @return 存储在桶中的地址
   */
  private int getIndex(K key, int length) {
    //获取hash code
    int hashCode = key.hashCode();
    //和桶数组长度取余
    int index = hashCode % length;
    return Math.abs(index);
  }


  /**
   * put方法
   *
   * @param key   key
   * @param value value
   */
  public void put(K key, V value) {
    //判断是否需要进行扩容
    if (size >= buckets.length * LOAD_FACTOR) {
      resize();
    }
    putVal(key, value, buckets);
  }

  /**
   * 将元素存入指定的node数组
   *
   * @param key   key
   * @param value value
   * @param table 存储桶
   */
  private void putVal(K key, V value, Node<K, V>[] table) {
    //获取位置
    int index = getIndex(key, table.length);
    Node<K, V> node = table[index];
    //插入的位置为空
    if (node == null) {
      table[index] = new Node<>(key, value);
      size++;
      return;
    }
    //插入位置不为空，说明发生冲突，使用链地址法,遍历链表
    while (node != null) {
      //如果key相同，就覆盖掉
      if ((node.key.hashCode() == key.hashCode())
          && (node.key == key || node.key.equals(key))) {
        node.value = value;
        return;
      }
      node = node.next;
    }
    //当前key不在链表中，插入链表头部
    Node<K, V> newNode = new Node<>(key, value, table[index]);
    table[index] = newNode;
    size++;
  }


  /**
   * 扩容
   */
  @SuppressWarnings("unchecked")
  private void resize() {
    //创建一个两倍容量的桶数组
    Node<K, V>[] newBuckets = new Node[buckets.length * 2];
    //将当前元素重新散列到新的桶数组
    rehash(newBuckets);
    buckets = newBuckets;
  }

  /**
   * 重新散列当前元素
   *
   * @param newBuckets 新的存储桶
   */
  private void rehash(Node<K, V>[] newBuckets) {
    //map大小重新计算
    size = 0;
    //将旧的桶数组的元素全部刷到新的桶数组里
    for (Node<K, V> bucket : buckets) {
      //为空，跳过
      if (bucket == null) {
        continue;
      }
      Node<K, V> node = bucket;
      while (node != null) {
        //将元素放入新数组
        putVal(node.key, node.value, newBuckets);
        node = node.next;
      }
    }
  }


  /**
   * 获取元素
   *
   * @param key key
   * @return 元素值
   */
  public V get(K key) {
    //获取key对应的地址
    int index = getIndex(key, buckets.length);
    if (buckets[index] == null) {
      return null;
    }
    Node<K, V> node = buckets[index];
    //查找链表
    while (node != null) {
      if ((node.key.hashCode() == key.hashCode())
          && (node.key == key || node.key.equals(key))) {
        return node.value;
      }
      node = node.next;
    }
    return null;
  }

  /**
   * 获取map长度
   *
   * @return 长度int
   */
  public int size() {
    return size;
  }

  @Override
  public String toString() {
    StringBuilder sb = new StringBuilder("{");
    for (Node<K,V> bucket : buckets) {
      Node<K,V> temp = bucket;
      while (temp != null) {
        sb.append(temp.key).append("=").append(temp.value).append(", ");
        temp = temp.next;
      }
    }
    sb.setCharAt(sb.length()-2, '}');
    sb.deleteCharAt(sb.length()-1);
    return sb.toString();
  }


}
